package info.fastpace.utils.iterator;

import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

import com.google.gdata.util.common.base.Pair;

public abstract class ParallelIterator<E> implements Iterator<E> {
	private List<? extends Iterator<E>> iterators;
	private Comparator<E> comparator;
	// Sorted - highest first
	private LinkedList<Pair<E, Iterator<E>>> nextItems = new LinkedList<Pair<E,Iterator<E>>>();
	private boolean initialized = false;

	public ParallelIterator() {
	}

	protected abstract Comparator<E> createComparator();

	protected abstract List<? extends Iterator<E>> createIterators();

	@Override
	public boolean hasNext() {
		if (!initialized) { // First time only
			iterators = createIterators();
			comparator = createComparator(); 
			for (Iterator<E> iterator : iterators) {
				addNewElement(iterator);
			}
			initialized = true;
		}

		return !nextItems.isEmpty();
	}

	@Override
	public E next() {
		if (!hasNext()) {
			throw new NoSuchElementException("No more elements");
		}
		Pair<E,Iterator<E>> pair = nextItems.removeFirst();
		E biggest = pair.first;
		addNewElement(pair.second);
		return biggest;
	}

	private void addNewElement(Iterator<E> iterator) {
		if (iterator.hasNext()) {
			E newItem = iterator.next();
			ListIterator<Pair<E, Iterator<E>>> mainIterator = nextItems.listIterator();
			while (mainIterator.hasNext()) {
				Pair<E, Iterator<E>> pair = mainIterator.next();
				E item = pair.first;
				if (comparator.compare(newItem, item) >= 0) {
					mainIterator.previous();
					break;
				}
			}
			Pair<E, Iterator<E>> newPair = Pair.of(newItem, iterator);
			mainIterator.add(newPair);
		}
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException("Remove method not supported in composite iterator");
	}

	public static class ParallelIteratorDefault<E> extends ParallelIterator<E> {
		private List<? extends Iterator<E>> iterators;
		private Comparator<E> comparator;

		public ParallelIteratorDefault(List<? extends Iterator<E>> iterators, Comparator<E> comparator) {
			this.iterators = iterators;
			this.comparator = comparator;
		}

		@Override
		protected final Comparator<E> createComparator() {
			return comparator;
		}

		@Override
		protected final List<? extends Iterator<E>> createIterators() {
			return iterators;
		}
	}
}
